#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

/*
只出现一次的数字 I
https://leetcode.cn/problems/single-number/
*/
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        int value = 0;
//        for (auto e : nums)
//        {
//            value ^= e;
//        }
//        return value;
//    }
//};

/*
只出现一次的数字 II
https://leetcode.cn/problems/single-number-ii/
*/

// 可以考虑从每个元素都出现三次入手。如果从次数入手，我们可以想到能不能和什么东西整除3挂钩。因为除了某个元素，其他元素都是三个三个为一组的。
// 我们可以注意到：-2^31 <= nums[i] <= 2^31 - 1，这意味着我们处理的数据都是32位的数据。如果把每一个数字都看成二进制，那么一个十进制数nums[i]对应一个32位的二进制数。将所有nums[i]对应的二进制数的对应位求和，将每一对应位的和值与3进行取模运算，得到的余数就是答案的对应二进制位的数值。这是因为除了答案本身，其它元素都是三个三个为一组的。


//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        int res = 0;
//        for (int i = 0; i < 32; i++)
//        {
//            int sum = 0;
//            for (auto& e : nums)
//            {
//                sum += ((e >> i) & 1);
//            }
//            if ((sum % 3) == 1)
//            {
//                res |= (1 << i);
//            }
//        }
//        return res;
//    }
//};


/*
只出现一次的数字 III
https://leetcode.cn/problems/single-number-iii/
*/

/*异或分组
已知x^x==0。定义数组的异或和为该数组所有元素的异或。
1. 求出nums的异或和xor，可知xor为两个目标元素的异或。
2. 找到xor中为1的二进制位，假设是第k位。这说明两个目标元素在第k位上不相同。
3. 根据第k位是0还是1，把nums分为两组，这样两个目标元素一定位于不同的组。
4. 分别求出两组的异或和，即得到两个目标元素。
 */
//class Solution {
//public:
//    vector<int> singleNumber(vector<int>& nums) {
//        vector<int>ans(2);
//        int value = 0;
//        for (auto& e : nums)
//        {
//            value ^= e;
//        }
//        int k = 0;
//        while ((value & 1) == 0)
//        {
//            value >>= 1;
//            ++k;
//        }
//        int ans1 = 0, ans2 = 0;
//        for (auto& e : nums)
//        {
//            if (((e >> k) & 1) == 0)
//            {
//                ans1 ^= e;
//            }
//            else
//            {
//                ans2 ^= e;
//            }
//        }
//        ans[0] = ans1;
//        ans[1] = ans2;
//        return ans;
//    }
//};